package org.example.everyday;

import javafx.geometry.Side;

import java.util.*;

/**
 *https://leetcode-cn.com/problems/jump-game-iv/
 * [100,-23,-23,404,100,23,23,23,3,404]
 * [0,  1,  2,  2,  1,  2, 3, 3, 4, 3]
 */
public class MinJumps {
    int INF = 0x3f3f3f3f;

    public static void main(String[] args) {
        int[] array = new int[]{100,-23,-23,404,100,23,23,23,3,404};

        MinJumps min=new MinJumps();
//        int result = min.minJumps(array);
        int result = min.jump1(array);
        System.out.println(result);
    }

    public  int minJumps(int[] arr){
        int n = arr.length;
        Map<Integer, List<Integer>> map = new HashMap<>();
        //倒序插入list,相当于给deque增加了一个同层【下标越大，优先出队】的作用
        for (int i = n-1; i >= 0; i--) {
            List<Integer> list = map.getOrDefault(arr[i],new ArrayList<>());
            list.add(i);
            map.put(arr[i],list);
        }
        int[] dist = new int[n];
        Arrays.fill(dist,INF);
        //声明一个队列
        Deque<Integer> d = new ArrayDeque<>();
        d.addLast(0);
        dist[0] = 0;
        while (!d.isEmpty()){
            int t = d.pollFirst(),step = dist[t];
            System.out.println("t:"+t+";step:"+step);
            if(t == n-1){
                for (Integer i:d){
                    System.out.println("d:"+d);
                }
                return step;
            }
            if(t+1<n && dist[t+1] == INF){
                d.addLast(t+1);
                dist[t+1] = step + 1;
            }
            if(t - 1>=0 && dist[t-1] == INF){
                d.addLast(t-1);
                dist[t-1] = step + 1;
            }
            List<Integer> list = map.getOrDefault(arr[t],new ArrayList<>());
            for (int ne:list){
                if(dist[ne] == INF){
                    d.addLast(ne);
                    dist[ne] = step + 1;
                }
            }
            map.remove(arr[t]);
        }
        return -1;
    }

    private void print(int[] arr){
        for (int i:arr){
            System.out.println("dict[i]:"+i);
        }
    }

    /**
     * 最小跳跃游戏
     * [100,-23,-23,404,100,23,23,23,3,404]
     * @param arr 要跳跃的数组
     * @return
     */
   public int jump1(int[] arr){
       //初始化一个map,存放相同的值和对应的下标
       Map<Integer,List<Integer>> map = new HashMap<Integer,List<Integer>>();
        for (int i=0;i<arr.length;i++){
            map.putIfAbsent(arr[i],new ArrayList<>());
            map.get(arr[i]).add(i);
        }

        Queue<int[]> queue = new ArrayDeque<int[]>();
        queue.add(new int[]{0,0});
        Set<Integer> vistedSet = new HashSet<Integer>();

        //如果队列中元素不为空  队列是先进先出
        while (!queue.isEmpty()){
            int[] queueItem = queue.poll();
            int idx = queueItem[0],step = queueItem[1];

            //终止条件 如果访问的索引已经到最后一个坐标，则说明已经访问到最后，可以跳出循环了
            if(idx == arr.length-1){
                return step;
            }
            step++;
            //如果map中包含了对应的 key ,key就是arr中的值
            if(map.containsKey(arr[idx])){
                //如果之前没有访问过这个元素
                    for (int i:map.get(arr[idx])) {
                        if(vistedSet.add(i)){
                            //走到每个下标，对应的步数
                            queue.offer(new int[]{i,step});
                        }
                    }
                //从map中移除掉，证明已经访问过了
                map.remove(arr[idx]);
            }

            if(idx+1<arr.length-1 && vistedSet.add(idx+1)){
                queue.offer(new int[]{idx+1,step});
            }
            if(idx-1>=0 && vistedSet.add(idx-1)){
                queue.offer(new int[]{idx-1,step});
            }
        }

        return -1;

   }


}
